package demo.DataStrucAndAlgo.Search;

import java.util.Arrays;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/28-07-28-9:42
 * @Description：demo.DataStrucAndAlgo.Search       斐波那契查找(黄金分割法查找)
 */
/*
斐波那契查找
    1、计算并保存一个斐波那契序列的数组，方便以后取值。数组名记为f，例如f[1]=1,f[2]=1,f[3]=2....
    2、把有序数组的长度尽可能扩充到接近data.length=f[k]-1,k是满足条件的最小值，比如数组长度为13，那么就把它长度扩充到f[8]-1=20
    所有在末尾添加的扩充元素都是原数组最后一个元素的复制品
    3、找到mid元素，不断进行二分比较，直到找到目标元素为止，这一步的做法与折半查找一模一样，仅仅是计算mid的公式从(low+high)/2改为low+(f[k-1]-1)
    4、再找到匹配的数据后，由于原数组被加长过，可能会出现mid处于加长部分的情况，但这部分实际在原数组中不存在，好在right仍然保存着原数组的有效边界，且加长空间内容
    都是最后一个数据，所以返回的索引应该在mid与right中谁小取谁
    为什么需要把数组长度扩充到f[k]-1而不是f[k]或者f[k+1]
    为了能正确递归计算mid值，f[k]-1 = (f[k-1]+f[k-2])-1=(f[k-1]-1)+1+(f[k-2]-1)
    中间的1就是我们二分的锚点mid，如果目标在左区，数组长度就缩到（f[k-1]-1）,如果在右区，数组长度就缩到（f[k--2]-1）
    否则就等于mid完成查找。而左区（f[k-1]-1）又能拆分成（f[k-2]-1）+1+(f[k-3]-1),右区（f[k-2]-1）又能被拆分成（f[k-3]-1）+1+(f[k-4]-1)
    这样递归分割下去就能不断的缩小区间直至找到目标
 */
public class fibSearch {
    public static final int SIZE = 20;    //定义斐波那契数组长度为20

    public static void main(String[] args) {
        int[] data = {1,2,3,4,5,6};
        System.out.println(fib_search(data,0,data.length-1,6));
    }

    public static int[] getFib(int[] data) {
        int f[] = new int[SIZE];
        f[0] = f[1] = 1;
        for (int i = 2; i < SIZE; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }

    public static int fib_search(int[] data, int left, int right, int num) {
        int k = 0;
        int[] f = getFib(data);   //获取斐波那契数组
        while(data.length-1 > f[k]-1){    //找到满足f[k]-1 >= data.length的最小值
            k++;
        }
        int[] temp = Arrays.copyOf(data,f[k]);   //对原有数据进行扩容，扩容空间数据为0
        System.out.println(Arrays.toString(temp));
        for (int i = data.length; i < temp.length - 1; i++) {    //将扩容空间所有数据用原数组的最后一个数据覆盖
            temp[i] = data[data.length-1];
        }
        while(left <= right){
            int mid = left + (f[k-1]-1);    //求中间数字
            if(num < temp[mid]){           //需要向左查找
                right = mid -1;
                k--;          //mid = left + f[k-1-1]-1
            }else if (num > temp[mid]){    //需要向右查找
                left = mid +1;
                k = k - 2;      //mid = left + f[k-1-2]-1
            }else{
                //由于原数组被加长过，可能会出现mid处于加长部分，但这部分实际在原数组中不存在
                //在right仍然保存着原数组的有效边界，且加长空间内容都是最后一个数据，所以mid与right中谁小取谁
                if(mid <= right){
                    return mid;
                }else{
                    return right;
                }
            }
        }
        return -1;
    }
}
